Drawing graphs.md (612B)
1 +++ 2 title = 'Drawing graphs' 3 +++ 4 # Drawing graphs 5 Embeddings: 6 7 - circular embedding — vertices are spaced evenly around a circle 8 - ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking 9 10 Planar graphs: graphs where no edges cross 11 12 - interior region: empty space enclosed by a cycle 13 - exterior region: empty space not enclosed by a cycle 14 - Euler’s formula for planar graphs: 15 - n-m+r=2 16 - n vertices, m edges, r regions 17 - condition for planar graph: m ≤ 3v-6 18 - every planar graph has a vertex *v, *with δ(*v*) ≤ 5